Peer-to-peer networking has proven to be a promising method for delivering live video streams and other content to a large number of clients over the Internet. Much effort has been devoted to the research and development of these live peer-to-peer streaming systems. Some deployed systems have shown that the peer-to-peer systems can scale to millions of online users in a single session.
In the design of the peer-to-peer streaming systems, one of the most important problems to address is how to organize the dynamic and heterogeneous peers into an efficient overlay. The structure and behavior of the overlay greatly affects the efficiency of many modules such as peer discovery, data transmission, and the final streaming performance perceived by end users.
Mesh-based and tree-based approaches are the two common methods for overlay construction in peer-to-peer streaming systems.
In the tree-based approach, peers or nodes (peers and nodes are used interchangeably throughout this document) form one or multiple trees to disseminate the streaming packets. Within each tree, the node receives packets from its parent nodes and delivers their copies to its child nodes. Multiple trees are usually disjointed, i.e., each node is an interior node of one tree and the leaf node of all the other trees. However, the tree is not robust to peer churn, since it requires high cost in repairing the tree structure when peers are joining and leaving the session frequently.
In the mesh-based approach, peers are organized in a more unstructured way. There is no explicit tree structure over the peers. Instead, peers simply find a number of other nodes as their partners and exchange data with them according to their available packets. Some research work has shown that the mesh-based approach is more robust and efficient than the tree-based one when delivering live video. Consequently, most deployed peer-to-peer streaming systems use mesh-based approaches.
However, current mesh-based approaches use a randomly constructed overlay to organize the peers for transmitting video, otherwise known as an undirected graph approach. Due to this undirected graph approach, it is difficult to describe the relationship between peers, the heterogeneity in the capability of the peers and the ability to optimize the overlay. As such, previous mesh-based and tree-based approaches are either not flexible or not robust enough for providing satisfactory performance.